package com.leetcode.offer;

import java.util.Arrays;

/**
 * @author zfl
 * @Classname MinArray
 * @Description 旋转数组的最小数字
 * @Date 2020/10/15 14:26
 */
public class MinArray {

    /**
     * @param numbers
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了45.37%的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了98.26%的用户
     */
    public static int minArray1(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }

    /**
     * @param numbers
     * @return
     * 二分法
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.1 MB, 在所有 Java 提交中击败了99.29%的用户
     */
    public static int minArray2(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if(numbers[mid] < numbers[high]) {
                high = mid;
            }else if(numbers[mid] > numbers[high]) {
                low = mid + 1;
            }else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}
